package com.algrithom.sort;

import java.util.Arrays;

import com.util.CommonUtil;

/**
 * 快速排序 步骤一：划分 (1)选择数组的尾元素做为支点，支点选择方案有很多。 (2)把>=支点的元素放到右边。 (3)把<=支点的元素放到左边。 (4)将支点放到正确的位置。 步骤二：递归
 * 对支点左右两边的子数组再分别调用步骤一，直到子数组长度为1。
 *
 * @author think
 * @version 1.0.0
 */
class FastSort {
    
    public static void main(String[] args){
        int[] array = {1,3,4,2,1,10,5};
        quickSort(array,0,array.length);
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * 快速排序
     *
     * @param array 数组
     */
    private static void quikSort(Integer[] array){
        recursiveQuikSort(array,0,array.length - 1);
    }
    
    /**
     * 递归的快速排序
     *
     * @param low 数组的最小下标
     * @param high 数组的最大下标
     */
    private static void recursiveQuikSort(Integer[] array,int low,int high){
        if (low < high) {
            // 以第一个元素为基准
            int pivot = array[low];
            // 对数组进行划分，比pivot小的元素在低位段，比pivot大的元素在高位段
            int partition = partition(array,low,high,pivot);
            
            CommonUtil.display(array);
            // 对划分后的低位段进行快速排序
            recursiveQuikSort(array,low,partition - 1);
            // 对划分后的高位段进行快速排序
            recursiveQuikSort(array,partition + 1,high);
        }
    }
    
    /**
     * 以pivot为基准对下标low到high的数组进行划分
     *
     * @param low 数组段的最小下标
     * @param high 数组段的最大下标
     * @param pivot 划分的基准元素
     * @return 划分完成后基准元素所在位置的下标
     */
    private static int partition(Integer[] array,int low,int high,int pivot){
        
        while (low < high) {
            // 从右端开始扫描，定位到第一个比pivot小的元素
            while (low < high && array[high] >= pivot) {
                high--;
            }
            CommonUtil.swap(array,low,high);
            
            // 从左端开始扫描，定位到第一个比pivot大的元素
            while (low < high && array[low] <= pivot) {
                low++;
            }
            CommonUtil.swap(array,low,high);
        }
        return low;
    }
    
    public static void quickSort(int[] arr,int low,int high){
        if (arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;
        
        // 挖坑1：保存基准的值
        int temp = arr[left];
        while (left < right) {
            // 坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            
            // 坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        // 基准值填补到坑3中，准备分治递归快排
        arr[left] = temp;
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr,low,left - 1);
        quickSort(arr,left + 1,high);
    }
}
